package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 1191. K 次串联后最大子数组之和
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/26 20:20
 */
public class KConcatenationMaxSum {

    public static void main(String[] args) {
        KConcatenationMaxSum test = new KConcatenationMaxSum();

        // 9
//        int[] arr = {1, 2};
//        int k = 3;

        // 2
//        int[] arr = {1,-2,1};
//        int k = 5;

        // 0
//        int[] arr = {-1,-2};
//        int k = 7;

        // 0
        int[] arr = {-1, 4, -2};
        int k = 7;

        int i = test.kConcatenationMaxSum(arr, k);
        System.out.println(i);
    }

    public int kConcatenationMaxSum(int[] arr, int k) {
        long item = 0L;
        long sum = 0L;
        long max = 0L;
        for (int i : arr) {
            sum += i;
            if (item + i > 0) {
                item += i;
            } else {
                item = 0L;
            }
            max = Math.max(max, item);
        }
        if (k == 1) {
            return (int) (max % 1000000007);
        }
        for (int i : arr) {
            if (item + i > 0) {
                item += i;
            } else {
                item = 0L;
            }
            max = Math.max(max, item);
        }
        if (k == 2 || sum <= 0) {
            return (int) (max % 1000000007);
        }
        return (int) ((sum % 1000000007 * (k - 2) + max) % 1000000007);
    }

}
